﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
/* Aho-Corasick text search algorithm implementation
 * 
 * For more information visit
 *		    
 */
namespace Jenvin.Library.DataStruct.Algorithm
{
    public class StringMatch
    {
        public class TreeNode
        {
            #region Constructor & Methods

            /// <summary>
            /// Initialize tree node with specified character
            /// </summary>
            /// <param name="parent">Parent node</param>
            /// <param name="c">Character</param>
            public TreeNode(TreeNode parent, char c)
            {
                _char = c;
                _parent = parent;
            }

            /// <summary>
            /// Adds pattern ending in this node
            /// </summary>
            /// <param name="result">Pattern</param>
            public void AddResult(string result)
            {
                if (_listResults.Contains(result)) return;
                _listResults.Add(result);
            }

            /// <summary>
            /// Adds trabsition node
            /// </summary>
            /// <param name="node">Node</param>
            public void AddTransition(TreeNode node)
            {
                _dicTransitions.Add(node.Char, node);
            }


            /// <summary>
            /// Returns transition to specified character (if exists)
            /// </summary>
            /// <param name="c">Character</param>
            /// <returns>Returns TreeNode or null</returns>
            public TreeNode GetTransition(char c)
            {
                TreeNode node=null;
                _dicTransitions.TryGetValue(c, out node);
                return node;
            }

            /// <summary>
            /// Returns true if node contains transition to specified character
            /// </summary>
            /// <param name="c">Character</param>
            /// <returns>True if transition exists</returns>
            public bool ContainsTransition(char c)
            {
                return _dicTransitions.ContainsKey(c);
            }

            #endregion
            #region Properties

            private char _char;
            private TreeNode _parent;
            private TreeNode _failure;//failure 函数。失败了往哪里转
            private List<string> _listResults = new List<string>();//结果。如果到达此结点有匹配测有保存结果 
            private System.Collections.Generic.Dictionary<char, TreeNode> _dicTransitions = new System.Collections.Generic.Dictionary<char, TreeNode>();//改结点下面有多个子结点
            /// <summary>
            /// Character
            /// </summary>
            public char Char
            {
                get { return _char; }
            }

            /// <summary>
            /// 父结点
            /// </summary>
            public TreeNode Parent
            {
                get { return _parent; }
            }

            /// <summary>
            /// Failure function - descendant node
            /// </summary>
            public TreeNode Failure
            {
                get { return _failure; }
                set { _failure = value; }
            }

            public IEnumerable<TreeNode> Transitions
            {
                get { return _dicTransitions.Values; }
            }

            public IEnumerable<string> Results
            {
                get { return _listResults; }
            }

            #endregion
        }
        private TreeNode _root = null;
        private string[] _keyWords = null;
        public StringMatch(string[] keyWords)
        {
            if (keyWords == null) throw new ArgumentException("keyWords");
            _keyWords = keyWords;
            BuildTree();
        }

        private void BuildTree()
        {
            // Build Trie Tree
            _root = new TreeNode(null, ' ');
            foreach (string p in _keyWords)
            {
                // add pattern to tree
                TreeNode nd = _root;
                foreach (char c in p)
                {
                    TreeNode ndNew = null;
                    foreach (TreeNode trans in nd.Transitions)
                        if (trans.Char == c) { ndNew = trans; break; }

                    if (ndNew == null)
                    {
                        ndNew = new TreeNode(nd, c);
                        nd.AddTransition(ndNew);
                    }
                    nd = ndNew;
                }
                nd.AddResult(p);//将结果 加到最后一个结点
            }

            // 确定  failure functions
            List<TreeNode> nodes = new List<TreeNode>();
            // level 1 nodes - fail to root node
            foreach (TreeNode nd in _root.Transitions)
            {
                nd.Failure = _root;
                foreach (TreeNode trans in nd.Transitions) nodes.Add(trans);
            }
            // other nodes - using BFS
            while (nodes.Count != 0)
            {
                List<TreeNode> newNodes = new List<TreeNode>();
                foreach (TreeNode nd in nodes)
                {
                    TreeNode r = nd.Parent.Failure;
                    char c = nd.Char;

                    while (r != null && !r.ContainsTransition(c)) r = r.Failure;
                    if (r == null)
                        nd.Failure = _root;
                    else
                    {
                        nd.Failure = r.GetTransition(c);
                        foreach (string result in nd.Failure.Results)
                            nd.AddResult(result);
                    }

                    // add child nodes to BFS list 
                    foreach (TreeNode child in nd.Transitions)
                        newNodes.Add(child);
                }
                nodes = newNodes;
            }
            _root.Failure = _root;
        }

        /// <summary>
        /// 匹配所以的结果 
        /// </summary>
        /// <param name="text"></param>
        /// <returns></returns>
        public Match[] Matches(string text)
        {
            List<Match> ret = new List<Match>();
            TreeNode ptr = _root;
            int index = 0;

            while (index < text.Length)
            {
                TreeNode trans = null;
                while (trans == null)
                {
                    trans = ptr.GetTransition(text[index]);
                    if (ptr == _root) break;
                    if (trans == null) ptr = ptr.Failure;
                }
                if (trans != null) ptr = trans;

                foreach (string found in ptr.Results)
                    ret.Add(new Match() { Index = index - found.Length + 1, Keyword = found });
                index++;
            }
            return ret.ToArray();
        }
        /// <summary>
        /// 匹配首次查找的结果 。如果没有找到返回 new Match() { Index = -1, Keyword = "" }
        /// </summary>
        /// <param name="text"></param>
        /// <returns></returns>
        public Match Matche(string text)
        {
            TreeNode ptr = _root;
            int index = 0;

            while (index < text.Length)
            {
                TreeNode trans = null;
                while (trans == null)
                {
                    trans = ptr.GetTransition(text[index]);
                    if (ptr == _root) break;
                    if (trans == null) ptr = ptr.Failure;
                }
                if (trans != null) ptr = trans;

                foreach (string found in ptr.Results)
                    return new Match() { Index = index - found.Length + 1, Keyword = found };
                index++;
            }
            return Match.Empty;
        }

        /// <summary>
        /// Searches passed text and returns true if text contains any keyword
        /// </summary>
        /// <param name="text">Text to search</param>
        /// <returns>True when text contains any keyword</returns>
        public bool ContainsAny(string text)
        {
            TreeNode ptr = _root;
            int index = 0;

            while (index < text.Length)
            {
                TreeNode trans = null;
                while (trans == null)
                {
                    trans = ptr.GetTransition(text[index]);
                    if (ptr == _root) break;
                    if (trans == null) ptr = ptr.Failure;
                }
                if (trans != null) ptr = trans;
                if (ptr.Results.Any()) return true;
                index++;
            }
            return false;
        }
    }
}
